      1  import java.util.Stack;

      2

      3  /**

      4     This program uses a stack to find a path from a position

      5     in a maze to an exit. It is assumed that the maze has no circular

      6     paths, and that there is at least one exit.

      7  */

      8  public class MazeSolver

      9  {

     10     public static void main(String[] args)

     11     {

     12        Maze maze = new Maze(

     13           new String[] {

     14              "*****************************",

     15              "** ***                      *",

     16              "** *** * ********************",

     17              "** *** *         *          *",

     18              "** *** * *******   **** *****",

     19              "**     * ************** *****",

     20              "****** ******* *******  *****",

     21              "******         ******* ******",

     22              "*      ******* ******* ******",

     23              "* **** ******* **           *",

     24              "*    ********* ******* ******",

     25              "* ****         ***     ******",

     26              "************** **************"});

     27

     28        solve(maze, 5, 8);

     29     }

     30

     31     /**

     32        Traverses a maze, printing out a path to the exit.

     33        @param maze the maze

     34        @param param the row of the starting position

     35        @param param the column of the starting position

     36     */

     37     public static void solve(Maze maze, int row, int column)

     38     {

     39        Stack<Path> s = new Stack<Path>();

     40        for (Path p : maze.pathsFrom(row, column))

     41        {

     42           s.push(p);

     43        }

     44

     45        while (s.size() > 0)

     46        {

     47           Path p = s.pop();

     48           System.out.println("Following " + p);

     49           int r = p.getEndingRow();

     50           int c = p.getEndingColumn();

     51           if (maze.isExit(r, c))

     52           {

     53              System.out.println("Exit!");

     54              return;

     55           }

     56           else if (maze.isDeadEnd(r, c))

     57           {

     58              System.out.println("Dead end");

     59           }

     60           else

     61           {

     62              for (Path p2 : maze.pathsFrom(r, c))

     63              {

     64                 if (!p2.isOpposite(p))

     65                 {

     66                    s.push(p2);

     67                 }

     68              }

     69           }

     70        }

     71     }

     72  }